package leetcode;


import java.util.*;

/**
 * @author qxf101
 */
public class Test {
    public static final int PATH_SIZE = 2;

    public static void main(String[] args) {
        int[] nums = new int[]{4, 4, 3, 2, 1};
        List<List<Integer>> result = combine(nums);
        System.out.println(result);
    }

    private static List<List<Integer>> combine(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        Deque<Integer> path = new ArrayDeque<>();

        dfs(nums, result, path, 0, 0);

        return result;
    }

    private static void dfs(int[] nums, List<List<Integer>> result, Deque<Integer> path, int start, int last) {
        if (path.size() >= PATH_SIZE) {
            if (path.getFirst() >= last) {
                List<Integer> ary = new ArrayList<>(path);
                Collections.sort(ary);
                result.add(ary);
            }
        }

        Set<Integer> temp = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (temp.contains(nums[i])) {
                continue;
            }

            temp.add(nums[i]);
            path.addFirst(nums[i]);

            dfs(nums, result, path, i + 1, nums[i]);
            path.removeFirst();
        }
    }
}

